package com.datastructures2.sort;

import java.util.Random;

import static com.datastructures2.sort.InsertSort.insertSort;

/**
 * @author MaoLin Wang
 * @date 2020/2/1822:56
 */
public class QuickSort {


    public static <T extends Comparable<? super T>>void testQuick(T[]arr){
        testQuick(arr,0,arr.length-1);
    }

    private static <T extends Comparable<? super T>> void testQuick(T[] arr, int left, int right) {
        if (right<=left){
            return;
        }
        int i=parti(arr,left,right);
        testQuick(arr,left,i-1);
        testQuick(arr,i+1,right);
    }

    private static <T extends Comparable<? super T>>int parti(T[] arr, int left, int right) {
        int l=left;
        int r=right+1;
        T pivot=arr[left];
        while(true){
            while (arr[++l].compareTo(pivot)<0){
                if (l>=right){
                    break;
                }
            }
            while (arr[--r].compareTo(pivot)>0){
                if (r<=left){
                    break;
                }
            }
            if (l>=r){
                break;
            }
            swapReferences(arr,l,r);
        }
        swapReferences(arr,left,r);
        return r;
    }

    private static<T extends Comparable<? super T>> void testSwap(T[] arr, int i, int j) {
        T temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }


    private static final int CUTOFF=15;
    public static <T extends Comparable<? super T>> void quickSort(T[] arr) {
        if (arr.length==0||arr.length==1){
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }

    private static  <T extends Comparable<? super T>>  void quickSort(T[] arr, int left, int right) {
        if (right<=left){
            return;
        }
        //此时j左边的元素已全部小于arr[j],j右边的元素全部小于arr[j]
        int j=partition(arr,left,right);
        quickSort(arr,left,j-1);
        quickSort(arr,j+1,right);

    }

    /**
     * 快速排序的切分
     * @param arr
     * @param left
     * @param right
     * @param <T>
     * @return
     */
    public static <T extends Comparable<? super T>> int partition(T[] arr, int left, int right) {

          int i=left,j=right+1;
            T pivot = arr[left];
            while (true){
                //循环直到找到一个比pivot大的值，或到达尾部
                while (arr[++i].compareTo(pivot)<0){
                    if (i==right){
                        break;
                    }
                }
                //循环直到找到一个比pivot小的值，或到达首部
                while (pivot.compareTo(arr[--j])<0){
                    if (j==left){
                        break;
                    }
                }
                //如果i和j相遇，则终止循环
                if (i>=j){
                    break;
                }
                //交换i和j的元素
                swapReferences(arr,i,j);
            }
            //将pivot换到j的位置
            swapReferences(arr,left,j);
            return j;

    }
    public static <T> void swapReferences(T[] arr,int index1,int index2){
        T temp=arr[index1];
        arr[index1]=arr[index2];
        arr[index2]=temp;
    }

    /**
     * 三取样切分
     * 维护一个指针lt，使得a[left]到a[lt-1]都小于切分元素v
     *
     * 一个指针gt，使得a[gt+1]到a[right]都大于切分元素v
     *
     * 一个指针i，使用a[lt]到a[i-1]都等于切分元素v
     *
     * 而a[i]到a[gt]元素尚未确定。
     *
     * 当i<=gt时循环：
     *
     * 1.a[i] < v: 将a[i]与a[lt]交换，并让 i 和 lt  加一，此时lt左边的一定小于v
     *
     * 2.a [i] > v: 将a[i]与a[gt]交换，并让 gt 减一，此时gt右边的一定大于v
     *
     * 3. a[i] = v : 直接让 i 加以 此时 lt  到 i-1 都等于v
     * @param arr
     * @param left
     * @param right
     * @param <T>
     */
    public static <T extends Comparable<? super T>> void quickSort3Way(T[] arr, int left, int right) {
        if (right<=left){
            return;
        }
        if (left+1<=right){
            //初始化三个指针
            int lt=left,i=lt+1,gt=right;
            T v = arr[left];
            while (i<=gt){
                int result=arr[i].compareTo(v);
                if (result<0){
                    swapReferences(arr,lt++,i++);
                }else if (result>0){
                    swapReferences(arr,i,gt--);
                }else {
                    i++ ;
                }
            }
            quickSort3Way(arr,left,lt-1);
            quickSort3Way(arr,gt+1,right);
        }else {
            insertSort(arr,left,right);
        }

    }
    private static <T extends Comparable<? super T>> T median3(T[] arr, int left, int right) {
        int mid=(left+right)/2;
        if (arr[mid].compareTo(arr[left])<0){
            swapReferences(arr,mid,left);
        }
        if (arr[right].compareTo(arr[left])<0){
            swapReferences(arr,right,left);
        }
        if (arr[right].compareTo(arr[mid])<0){
            swapReferences(arr,mid,right);
        }
        HeapSort.swap(arr,mid,right-1);
        return arr[right-1];
    }

    public static void main(String[] args) {
        Integer [] arr={-21,312,44,11,-23,2,10};
        testQuick(arr);
        for(Integer i:arr){
            System.out.println(i);
        }
      /*Integer[]arr=new Integer[8000000];
        Random random=new Random();
        for (int i = 0; i < 4000000; i++) {
            arr[i]=1;
        }
        for (int i = 400000; i < 8000000; i++) {
            arr[i]=random.nextInt(8000000);
        }
        long b=System.currentTimeMillis();
        Quick3Way.sort(arr);
        long e=System.currentTimeMillis();
        System.out.println(e-b);
*/
    }
}
